package Hot100.Medium.Sort;

public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        // 创建临时数组，避免在递归中重复创建
        int[] temp = new int[arr.length];
        divideAndMerge(arr, 0, arr.length - 1, temp);
    }

    private static void divideAndMerge(int[] arr, int start, int end, int[] temp) {
        // 递归终止条件：只有一个元素或没有元素
        if (start >= end) return;

        // 1. 分：找到中间点
        int mid = start + (end - start) / 2;

        // 2. 递归排序左右两部分
        divideAndMerge(arr, start, mid, temp);
        divideAndMerge(arr, mid + 1, end, temp);

        // 3. 合：合并两个有序数组
        merge(arr, start, mid, end, temp);
    }

    private static void merge(int[] arr, int start, int mid, int end, int[] temp) {
        int left = start;      // 左半部分指针
        int right = mid + 1;   // 右半部分指针
        int index = start;     // 临时数组指针

        // 合并两个都有元素的有序数组，结束时最多只有一个子数组还有剩余元素
        while (left <= mid && right <= end) {
            temp[index++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
        }

        // 复制剩余元素
        while (left <= mid) temp[index++] = arr[left++];
        while (right <= end) temp[index++] = arr[right++];

        // 拷贝回原数组
        for (int i = start; i <= end; i++) {
            arr[i] = temp[i];
        }
    }
}
